home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Mac Game Programming Gurus / TricksOfTheMacGameProgrammingGurus.iso / CodeWarrior Lite / Metrowerks C⁄C++ Lite / Headers / STL Headers / iterator.h < prev    next >
Encoding:
C/C++ Source or Header  |  1995-04-24  |  11.6 KB  |  396 lines  |  [TEXT/MMCC]
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  */
  15.  
  16. #ifndef ITERATOR_H
  17. #define ITERATOR_H
  18.  
  19. #include <stddef.h>
  20. //#include <iostream.h>
  21. #include <bool.h>
  22. #include <function.h>
  23.  
  24. struct input_iterator_tag {};
  25. struct output_iterator_tag {};
  26. struct forward_iterator_tag {};
  27. struct bidirectional_iterator_tag {};
  28. struct random_access_iterator_tag {};
  29.  
  30. template <class T, class Distance> struct input_iterator {};
  31. struct output_iterator {};
  32. template <class T, class Distance> struct forward_iterator {};
  33. template <class T, class Distance> struct bidirectional_iterator {};
  34. template <class T, class Distance> struct random_access_iterator {};
  35.  
  36. template <class T, class Distance> 
  37. inline input_iterator_tag 
  38. iterator_category(const input_iterator<T, Distance>&) {
  39.     return input_iterator_tag();
  40. }
  41.  
  42. inline output_iterator_tag iterator_category(const output_iterator&) {
  43.     return output_iterator_tag();
  44. }
  45.  
  46. template <class T, class Distance> 
  47. inline forward_iterator_tag
  48. iterator_category(const forward_iterator<T, Distance>&) {
  49.     return forward_iterator_tag();
  50. }
  51.  
  52. template <class T, class Distance> 
  53. inline bidirectional_iterator_tag
  54. iterator_category(const bidirectional_iterator<T, Distance>&) {
  55.     return bidirectional_iterator_tag();
  56. }
  57.  
  58. template <class T, class Distance> 
  59. inline random_access_iterator_tag
  60. iterator_category(const random_access_iterator<T, Distance>&) {
  61.     return random_access_iterator_tag();
  62. }
  63.  
  64. template <class T>
  65. inline random_access_iterator_tag iterator_category(const T*) {
  66.     return random_access_iterator_tag();
  67. }
  68.  
  69. template <class T, class Distance> 
  70. inline T* value_type(const input_iterator<T, Distance>&) {
  71.     return (T*)(0); 
  72. }
  73.  
  74. template <class T, class Distance> 
  75. inline T* value_type(const forward_iterator<T, Distance>&) {
  76.     return (T*)(0);
  77. }
  78.  
  79. template <class T, class Distance> 
  80. inline T* value_type(const bidirectional_iterator<T, Distance>&) {
  81.     return (T*)(0);
  82. }
  83.  
  84. template <class T, class Distance> 
  85. inline T* value_type(const random_access_iterator<T, Distance>&) {
  86.     return (T*)(0);
  87. }
  88.  
  89. template <class T>
  90. inline T* value_type(const T*) { return (T*)(0); }
  91.  
  92. template <class T, class Distance> 
  93. inline Distance* distance_type(const input_iterator<T, Distance>&) {
  94.     return (Distance*)(0);
  95. }
  96.  
  97. template <class T, class Distance> 
  98. inline Distance* distance_type(const forward_iterator<T, Distance>&) {
  99.     return (Distance*)(0);
  100. }
  101.  
  102. template <class T, class Distance> 
  103. inline Distance* 
  104. distance_type(const bidirectional_iterator<T, Distance>&) {
  105.     return (Distance*)(0);
  106. }
  107.  
  108. template <class T, class Distance> 
  109. inline Distance* 
  110. distance_type(const random_access_iterator<T, Distance>&) {
  111.     return (Distance*)(0);
  112. }
  113.  
  114. template <class T>
  115. inline ptrdiff_t* distance_type(const T*) { return (ptrdiff_t*)(0); }
  116.  
  117. template <class Container>
  118. class back_insert_iterator : public output_iterator {
  119. protected:
  120.     Container& container;
  121. public:
  122.     back_insert_iterator(Container& x) : container(x) {}
  123.     back_insert_iterator<Container>&
  124.     operator=(const Container::value_type& value) { 
  125.     container.push_back(value);
  126.     return *this;
  127.     }
  128.     back_insert_iterator<Container>& operator*() { return *this; }
  129.     back_insert_iterator<Container>& operator++() { return *this; }
  130.     back_insert_iterator<Container>& operator++(int) { return *this; }
  131. };
  132.  
  133. template <class Container>
  134. back_insert_iterator<Container> back_inserter(Container& x) {
  135.     return back_insert_iterator<Container>(x);
  136. }
  137.  
  138. template <class Container>
  139. class front_insert_iterator : public output_iterator {
  140. protected:
  141.     Container& container;
  142. public:
  143.     front_insert_iterator(Container& x) : container(x) {}
  144.     front_insert_iterator<Container>&
  145.     operator=(const Container::value_type& value) { 
  146.     container.push_front(value);
  147.     return *this;
  148.     }
  149.     front_insert_iterator<Container>& operator*() { return *this; }
  150.     front_insert_iterator<Container>& operator++() { return *this; }
  151.     front_insert_iterator<Container>& operator++(int) { return *this; }
  152. };
  153.  
  154. template <class Container>
  155. front_insert_iterator<Container> front_inserter(Container& x) {
  156.     return front_insert_iterator<Container>(x);
  157. }
  158.  
  159. template <class Container>
  160. class insert_iterator : public output_iterator {
  161. protected:
  162.     Container& container;
  163.     Container::iterator iter;
  164. public:
  165.     insert_iterator(Container& x, Container::iterator i) 
  166.     : container(x), iter(i) {}
  167.     insert_iterator<Container>&
  168.     operator=(const Container::value_type& value) { 
  169.     iter = container.insert(iter, value);
  170.     ++iter;
  171.     return *this;
  172.     }
  173.     insert_iterator<Container>& operator*() { return *this; }
  174.     insert_iterator<Container>& operator++() { return *this; }
  175.     insert_iterator<Container>& operator++(int) { return *this; }
  176. };
  177.  
  178. template <class Container, class Iterator>
  179. insert_iterator<Container> inserter(Container& x, Iterator i) {
  180.     return insert_iterator<Container>(x, Container::iterator(i));
  181. }
  182.  
  183. template <class BidirectionalIterator, class T, class Reference, 
  184.           class Distance> 
  185. // Reference = T& 
  186. // Distance = ptrdiff_t
  187. class reverse_bidirectional_iterator 
  188.     : public bidirectional_iterator<T, Distance> {
  189.     typedef reverse_bidirectional_iterator<BidirectionalIterator, T, Reference,
  190.                                            Distance> self;
  191.     friend bool operator==(const self& x, const self& y);
  192. protected:
  193.     BidirectionalIterator current;
  194. public:
  195.     reverse_bidirectional_iterator() {}
  196.     reverse_bidirectional_iterator(BidirectionalIterator x) : current(x) {}
  197.     BidirectionalIterator base() { return current; }
  198.     Reference operator*() const {
  199.     BidirectionalIterator tmp = current;
  200.     return *--tmp;
  201.     }
  202.     self& operator++() {
  203.     --current;
  204.     return *this;
  205.     }
  206.     self operator++(int) {
  207.     self tmp = *this;
  208.     --current;
  209.     return tmp;
  210.     }
  211.     self& operator--() {
  212.     ++current;
  213.     return *this;
  214.     }
  215.     self operator--(int) {
  216.     self tmp = *this;
  217.     ++current;
  218.     return tmp;
  219.     }
  220. };
  221.  
  222. template <class BidirectionalIterator, class T, class Reference,
  223.           class Distance>
  224. inline bool operator==(
  225.     const reverse_bidirectional_iterator<BidirectionalIterator, T, Reference,
  226.                                  Distance>& x, 
  227.     const reverse_bidirectional_iterator<BidirectionalIterator, T, Reference,
  228.                                  Distance>& y) {
  229.     return x.current == y.current;
  230. }
  231.  
  232. template <class RandomAccessIterator, class T, class Reference,
  233.           class Distance> 
  234. // Reference = T&
  235. // Distance = ptrdiff_t
  236. class reverse_iterator : public random_access_iterator<T, Distance> {
  237.     typedef reverse_iterator<RandomAccessIterator, T, Reference, Distance>
  238.     self;
  239.     friend bool operator==(const self& x, const self& y);
  240.     friend bool operator<(const self& x, const self& y);
  241.     friend Distance operator-(const self& x, const self& y);
  242.     friend self operator+(Distance n, const self& x);
  243. protected:
  244.     RandomAccessIterator current;
  245. public:
  246.     reverse_iterator() {}
  247.     reverse_iterator(RandomAccessIterator x) : current(x) {}
  248.     RandomAccessIterator base() { return current; }
  249.     Reference operator*() const { return *(current - 1); }
  250.     self& operator++() {
  251.     --current;
  252.     return *this;
  253.     }
  254.     self operator++(int) {
  255.     self tmp = *this;
  256.     --current;
  257.     return tmp;
  258.     }
  259.     self& operator--() {
  260.     ++current;
  261.     return *this;
  262.     }
  263.     self operator--(int) {
  264.     self tmp = *this;
  265.     ++current;
  266.     return tmp;
  267.     }
  268.     self operator+(Distance n) const {
  269.     return self(current - n);
  270.     }
  271.     self& operator+=(Distance n) {
  272.     current -= n;
  273.     return *this;
  274.     }
  275.     self operator-(Distance n) const {
  276.     return self(current + n);
  277.     }
  278.     self& operator-=(Distance n) {
  279.     current += n;
  280.     return *this;
  281.     }
  282.     Reference operator[](Distance n) { return *(*this + n); }
  283. };
  284.  
  285. template <class RandomAccessIterator, class T, class Reference, class Distance>
  286. inline bool operator==(const reverse_iterator<RandomAccessIterator, T,
  287.                                       Reference, Distance>& x, 
  288.                const reverse_iterator<RandomAccessIterator, T,
  289.                                       Reference, Distance>& y) {
  290.     return x.current == y.current;
  291. }
  292.  
  293. template <class RandomAccessIterator, class T, class Reference, class Distance>
  294. inline bool operator<(const reverse_iterator<RandomAccessIterator, T,
  295.                                      Reference, Distance>& x, 
  296.               const reverse_iterator<RandomAccessIterator, T,
  297.                                      Reference, Distance>& y) {
  298.     return y.current < x.current;
  299. }
  300.  
  301. template <class RandomAccessIterator, class T, class Reference, class Distance>
  302. inline Distance operator-(const reverse_iterator<RandomAccessIterator, T,
  303.                                      Reference, Distance>& x, 
  304.               const reverse_iterator<RandomAccessIterator, T,
  305.                                      Reference, Distance>& y) {
  306.     return y.current - x.current;
  307. }
  308.  
  309. template <class RandomAccessIterator, class T, class Reference, class Distance>
  310. inline reverse_iterator<RandomAccessIterator, T, Reference, Distance> 
  311. operator+(Distance n,
  312.       const reverse_iterator<RandomAccessIterator, T, Reference,
  313.                              Distance>& x) {
  314.     return reverse_iterator<RandomAccessIterator, T, Reference, Distance>
  315.     (x.current - n);
  316. }
  317.  
  318.  
  319. template <class OutputIterator, class T>
  320. class raw_storage_iterator : public output_iterator {
  321. protected:
  322.     OutputIterator iter;
  323. public:
  324.     raw_storage_iterator(OutputIterator x) : iter(x) {}
  325.     raw_storage_iterator<OutputIterator, T>& operator*() { return *this; }
  326.     raw_storage_iterator<OutputIterator, T>& operator=(const T& element) {
  327.     construct(iter, element);
  328.     return *this;
  329.     }        
  330.     raw_storage_iterator<OutputIterator, T>& operator++() {
  331.     ++iter;
  332.     return *this;
  333.     }
  334.     raw_storage_iterator<OutputIterator, T> operator++(int) {
  335.     raw_storage_iterator<OutputIterator, T> tmp = *this;
  336.     ++iter;
  337.     return tmp;
  338.     }
  339. };
  340.  
  341.  
  342. template <class T, class Distance> // Distance == ptrdiff_t
  343. class istream_iterator : public input_iterator<T, Distance> {
  344. friend bool operator==(const istream_iterator<T, Distance>& x,
  345.                const istream_iterator<T, Distance>& y);
  346. protected:
  347.     istream* stream;
  348.     T value;
  349.     bool end_marker;
  350.     void read() {
  351.     end_marker = (*stream) ? true : false;
  352.     if (end_marker) *stream >> value;
  353.     end_marker = (*stream) ? true : false;
  354.     }
  355. public:
  356.     istream_iterator() : stream(&cin), end_marker(false) {}
  357.     istream_iterator(istream& s) : stream(&s) { read(); }
  358.     const T& operator*() const { return value; }
  359.     istream_iterator<T, Distance>& operator++() { 
  360.     read(); 
  361.     return *this;
  362.     }
  363.     istream_iterator<T, Distance> operator++(int)  {
  364.     istream_iterator<T, Distance> tmp = *this;
  365.     read();
  366.     return tmp;
  367.     }
  368. };
  369.  
  370. template <class T, class Distance>
  371. bool operator==(const istream_iterator<T, Distance>& x,
  372.         const istream_iterator<T, Distance>& y) {
  373.     return x.stream == y.stream && x.end_marker == y.end_marker ||
  374.     x.end_marker == false && y.end_marker == false;
  375. }
  376.  
  377. template <class T>
  378. class ostream_iterator : public output_iterator {
  379. protected:
  380.     ostream* stream;
  381.     char* string;
  382. public:
  383.     ostream_iterator(ostream& s) : stream(&s), string(0) {}
  384.     ostream_iterator(ostream& s, char* c) : stream(&s), string(c)  {}
  385.     ostream_iterator<T>& operator=(const T& value) { 
  386.     *stream << value;
  387.     if (string) *stream << string;
  388.     return *this;
  389.     }
  390.     ostream_iterator<T>& operator*() { return *this; }
  391.     ostream_iterator<T>& operator++() { return *this; } 
  392.     ostream_iterator<T>& operator++(int) { return *this; } 
  393. };
  394.  
  395. #endif
  396.